#
# @lc app=leetcode.cn id=968 lang=python3
#
# [968] 监控二叉树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if node is None:
                return inf, 0, 0 # 当前node为空,inf表示无法安装监控
            left_camera, left_parent, left_child = dfs(node.left)
            right_camera, right_parent, right_child = dfs(node.right)
            node_camera = min(left_camera, left_parent, left_child) + min(right_camera, right_parent, right_child) + 1
            node_parent = min(left_camera, left_child) + min(right_camera, right_child)
            node_child = min(left_camera+right_child, right_camera+left_child, left_camera+right_camera)
            
            return node_camera, node_parent, node_child
        root_camera, root_parent, root_child = dfs(root)
        return min(root_camera, root_child)
# @lc code=end

